package leetcode.erfen;


public class MySqrt {
    public static void main(String[] args) {
        System.out.println(new MySqrt().mySqrt(16));
    }
    public int mySqrt(int x) {
        if(x==0)
            return 0;

        int l=1, r = x;
        while (l<=r) {
            int mid = l + (r - l) / 2;

            int sqrt = x / mid;

            if (sqrt == mid)
                return mid;

            else if (mid > sqrt)
                r = mid - 1;
            else
                l = mid + 1;
        }
        return  r;
    }
}